package com.cuz.daileetcode;

/**
 * @author cuzz
 * @version 1.0
 * @description: 给定一个有序数组arr
 * 代表数组中的从左到右的n个点arr[0],arr[1],arr[2]...arr[n-1]
 * 给点一个正数L代表长度 为L的绳子，求绳子最多覆盖多少个点
 * @date 17:54 2022/2/7
 **/
public class Day40 {

    /****
     * 二分法
     *
     * 假设绳子的右端位于数轴中的一个点上(此点的位置为index1
     * 那么数的大小是arr[index])
     * 使用二分法查找最左侧 能被绳子覆盖到的数，离index1最远的下标记为index2
     * （数应该大于等于 arr[index]-L,尽量更小一点）
     * 那么绳子可以覆盖数的个数是 num=index1-index2+1
     *
     * 循环对每个数进行这个操作 统计 Max(num)即可
     *
     * 时间复杂度 对N一个数进行循环，
     * 使用二分法查找时间复杂度为logN
     * 总时间复杂度为N logN
     *
     * 空间复杂度 O（1）常数个临时变量
     */
    static class BinarySearch {

        public static void main(String[] args) {
            int[] ints = {1, 3, 5, 6, 7, 8, 11};
            int l = 5;
            int i = numTheRopeCanCover(ints, l);
            System.out.println(i);
        }

        /****
         * 绳子可以覆盖的数的个数
         * @param arr 升序数组
         * @param len 绳子长度
         * @return 可以覆盖的个数
         */
        static int numTheRopeCanCover(int[] arr, int len) {
            if (len <= 0 || arr == null || arr.length == 0) {
                return 0;
            }
            int maxNum = 0;
            for (int index1 = 0; index1 < arr.length; index1++) {
                int index2 = binarySearchFindLeftNumGreaterEqual(arr, index1, arr[index1] - len);
                maxNum = Math.max(index1 - index2 + 1, maxNum);
            }
            return maxNum;
        }

        /**
         * 二分查找，
         *
         * @param arr           数组
         * @param indexLessThen 找到数的下标必须小于 indexLessThen
         * @param numShouldGE   找到的数应该大于等于这个数
         * @return 符合条件数最小下标
         */
        static int binarySearchFindLeftNumGreaterEqual(int[] arr, int indexLessThen, int numShouldGE) {
            int left = 0;
            int right = indexLessThen;
            while (left <= right) {
                //求中点 忽略溢出
                int mid = ((right - left) >> 1) + left;
                //满足我们要的条件 但是我们要找最小的 那么 right=mid-1
                if (arr[mid] >= numShouldGE) {
                    right = mid - 1;
                } else {
                    //否则不符合条件 left右移动
                    left = mid + 1;
                }
            }
            //如果 满足 搜索的条件 那么我们 返回left
            //保证left是最左且 大于等于当前的数  numShouldGE
            if (arr[left] >= numShouldGE) {
                return left;
            }
            //否则是没找到哦
            return -1;
        }
    }

    /**
     * 滑动窗口
     * 窗口的左边界记为L，右边界记为R
     * L,R 初始化为0
     *
     * 如果 arr[R]-arr[L]<=绳子长度l 那么R++ 表示还可以容纳更多数
     *
     * 否则 代表已经超过了绳子的长度 此时 L——R-1中的数 可以位于绳子内，
     * 绳子中可以包含的数为R-1-L+1 =R-L 然后我们更新结果
     */
    static class SlidingWindow {
        public static void main(String[] args) {
            int[] ints = {1, 3, 5, 6, 7, 8,9, 11};
            int l = 2;
            int i = numTheRopeCanCover(ints, l);
            System.out.println(i);
        }

        /****
         * 绳子可以覆盖的数的个数
         * @param arr 升序数组
         * @param len 绳子长度
         * @return 可以覆盖的个数
         */
        static int numTheRopeCanCover(int[] arr, int len) {
            if (len <= 0 || arr == null || arr.length == 0) {
                return 0;
            }
            int maxNum = 0;
            int left = 0;
            int right = 0;
            for (int ignored : arr) {
                if (arr[right] - arr[left] > len) {
                    maxNum = Math.max(maxNum, right - left);
                    left++;
                } else {
                    right++;
                }
            }
            return maxNum;
        }
    }
}
